class TopK {

    public int[] smallestK(int[] arr,int k){
        if(k == 0){
            return new int[0];
        }

        int[] countK = new int[k];
        for (int i = 0; i < k; i++) {
            countK[i] = arr[i];
        }

        int lastNonLeaf = (countK.length - 1) / 2 ;
        for (int i = lastNonLeaf; i >= 0; i--) {
            shifDown(countK, i, countK.length);
        }

        for (int i = k; i < arr.length; i++) {
            if(countK[0] > arr[i]){
                countK[0] = arr[i];
                shifDown(countK, 0, countK.length);
            }
        }

        selectSort(countK);
        return countK;
    }

        // 大堆
    private void shifDown(int[] array,int parent,int usedSize){
        int child = parent * 2 + 1;
        while (child < usedSize){
            if(child + 1 < usedSize && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[parent]){
                Swap(array,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    private void Swap(int[] array, int child, int parent) {
        int tmp = array[child];
        array[child] = array[parent];
        array[parent] = tmp;
    }

    public void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            Swap(array,i,minIndex);
        }
    }
}